Description

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

  • You may only use constant extra space.

For example,
Given the following binary tree,

1
2
3
4
5
     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

1
2
3
4
5
     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

 

Solution

通过BFS层序遍历节点，只要遍历过程中维护当前节点的前一个节点pre，每次将pre中的next指向当前节点就能将所有节点根据层序遍历的次序串起来，只要在将每层最右边的节点的next指针赋值为空即可。

对于前一题[Populating Next Right Pointers in Each Node]，由于题目限定了测试用例均为满二叉树，因此只要从根节点出发，一直沿着右子树依次将途径的节点的next赋值为空后所有指针满足条件。

本题条件相比上一题缺少了满二叉树的限定，每层的最右端的节点未必是父节点的右孩子，因此需要维护每层最右端的节点。解中采取的方法是开一个数组vec[n]存放第n层最右端的节点。由于层序遍历时可以控制在每层中依次从左至右遍历节点，因此在遍历时将当前节点覆盖到记录最右端节点的数组中即可，最右端的节点将不会被覆盖。

题中暗示本题和前一题最优空间复杂度为O(1)，上述解法为O(n)，有待进一步思考。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct LevelNode
{
    int level;
    struct TreeLinkNode* Node;
};
class Solution {
public:
    void connect(TreeLinkNode *root)
    {
        if(root == NULL) return;
        queue<LevelNode> Q;
        vector<TreeLinkNode*> vec;
        LevelNode first = {0, root};
        Q.push(first);
        LevelNode pre = first;
        while(!Q.empty())
        {
            LevelNode t = Q.front();
            Q.pop();
            if(t.level == (int)vec.size())
            {
                vec.push_back(t.Node);
            }
            else
            {
                vec[t.level] = t.Node;
            }
            pre.Node->next = t.Node;
            pre = t;
            if(t.Node->left)
            {
                LevelNode nt = {t.level + 1, t.Node->left};
                Q.push(nt);
            }
            if(t.Node->right)
            {
                LevelNode nt = {t.level + 1, t.Node->right};
                Q.push(nt);
            }
        }
        for(int i = 0; i < (int)vec.size(); i++)
        {
            vec[i]->next = NULL;
        }
    }
};